package Heap;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    public static int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        int i = 0;
        //建立一个大小为k的最大堆
        while (i < k) {
            priorityQueue.offer(arr[i]);
            i++;
        }
        //堆顶大于arr[i]，则堆顶一定不属于最小的topK，出堆
        while (i < arr.length) {
            int cmp = priorityQueue.peek();
            if (cmp > arr[i]) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
            i++;
        }
        i = 0;
        //一定要初始化数组的大小不然会OutOfIndexBound
        int[] ret = new int[k];
        while (!priorityQueue.isEmpty()) {
            ret[i++] = priorityQueue.poll();
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] arr = new int[] {1,3,5,7,2,4,6,8};
        int[] ret = smallestK(arr, 4);
        for (int x:
             ret) {
            System.out.print(x + " ");
        }
    }
}
